Big O Notation.md (1473B)
1 +++ 2 title = 'Big O Notation' 3 template = 'page-math.html' 4 +++ 5 # Big O Notation 6 used to classify algorithms 7 function characterisation according to rates of growth 8 useful for analysing efficiency 9 always uses approximate worst case 10 read “order of" 11 12 Example: 13 - $T(n)=4n^2-2n+2$ 14 - $n=500$ => $4n^2$ is 1000 times larger than 2n 15 - $T(n) = O(n^2)$ 16 17 ## Time complexity 18 expressed in Big O notation 19 performance: how much time, memory, disk, etc. 20 21 time complexity: amount of time taken by an algorithm to run, as a function of the length of the string representing the input 22 23 typically interested in worst-case time complexity T(*n*) 24 25 Determining complexities: 26 27 - sequence of statements: 28 - T=t(statement 1)+t(statement 2)+…+t(statement k) 29 - if simple, time for each statement is constant, so total time is constant 30 - therefore T(*n*) = O(1) 31 - if-then-else 32 - worst case is the slower of two possibilities 33 - max(time(block1), time(block2)) 34 - if block1 takes O(1) and block2 takes O(N), it will be O(N) 35 - loops 36 - loop executes N times, so sequence of statements also executes N times 37 - if assume statements are O(1), total time is N\*O(1) 38 - so O(N) 39 - nested loops 40 - if N is times for outer loop, and M is times for inner loop 41 - executes total of N\*M times 42 - so complexity is O(N\*M) 43 - function/procedure calls 44 - f(k) has O(1) 45 - g(k) has O(k) 46 - if a loop goes 1 .. N and calls g(J) every time 47 - complexity of O(N)²